package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
	result := 0
	var dfs func(root *TreeNode) int 
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		left := dfs(root.Left)
		right := dfs(root.Right)
		if left + right + 1 > result {
			result = left + right + 1
		}
		if left > right {
			return left + 1
		}
		return right + 1
	}
	dfs(root)
	return result - 1
}

func main() {
	root:= &TreeNode{
		Val: 1,
		Right: &TreeNode{
			Val: 3,
		},
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{Val: 4},
			Right: &TreeNode{Val: 5},
		},
	}
	println(diameterOfBinaryTree(root))
}
